home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / smail-3.1.28 / src / hash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-11  |  9.6 KB  |  266 lines
  1. /* @(#)src/hash.h    1.6 7/11/92 11:49:20 */
  2.  
  3. /*
  4.  *    Copyright (C) 1987, 1988 Ronald S. Karr and Landon Curt Noll
  5.  *    Copyright (C) 1992  Ronald S. Karr
  6.  * 
  7.  * See the file COPYING, distributed with smail, for restriction
  8.  * and warranty information.
  9.  */
  10.  
  11. /*
  12.  * hash:
  13.  *    definitions for the support of hash.c
  14.  */
  15.  
  16. /*
  17.  * hash function values
  18.  */
  19. /* shift the hash up HASH_UP_SHIFT bits before adding the next character */
  20. #define HASH_UP_SHIFT (3)
  21. /* if hash mod < (1<<HASH_LEVEL_SHIFT), use L_ hash values, otherwise H_ */
  22. #define HASH_LEVEL_SHIFT (17)
  23. #define HASH_LEVEL (1<<HASH_LEVEL_SHIFT)
  24. /* for hash sizes where the hash mod < HASH_LEVEL */
  25. #define L_MASK_SHIFT (HASH_LEVEL_SHIFT)
  26. #define L_HASH_MASK (~((1<<L_MASK_SHIFT)-1))     /* mask of excess bits */
  27. #define L_DOWN_SHIFT (L_MASK_SHIFT-1)         /* shift down excess */
  28. /* for hash sizes where the hash mod >= HASH_LEVEL */
  29. #define H_MASK_SHIFT (BITS_PER_LONG-HASH_UP_SHIFT-2)
  30. #define H_HASH_MASK (~((1<<H_MASK_SHIFT)-1))     /* mask of excess bits */
  31. #define H_DOWN_SHIFT (H_MASK_SHIFT-2)         /* shift down excess */
  32.  
  33. /*
  34.  * what add_to_hash(), lookup_in_hash(), ... return
  35.  */
  36. #define NOT_HASHED (-1)        /* the key was not hashed */
  37. #define JUST_HASHED (0)        /* the key was just hashed */
  38. #define ALREADY_HASHED (1)    /* the key has been already hashed */
  39.  
  40. /*
  41.  * hash_table - hash slots which map integers to mixed chains of hash elements
  42.  *
  43.  * A hash table consists of a ``struct hash_table'' and related hash slot
  44.  * chains of ``struct hash''.  A hash table contains the number of slots,
  45.  * and that number of slot pointers.  Each slot points to a slot chain
  46.  * of ``struct hash'' elements.  Hash slot chains are kept in sorted order.
  47.  *
  48.  * The function hash_str() maps a string the index of one of the hash table
  49.  * slot pointers.  A slot that does not have a chain has the value NULL.
  50.  */
  51. struct hash_table {
  52.     int len;        /* the number of hash slots in this table */
  53.     int flags;        /* see flags section, default == 0 */
  54.     int indx;        /* the walk_hash() slot location */
  55.     struct hash *prev;    /* the walk_hash() current element location */
  56.     struct block *life;    /* the malloc block storage belongs to */
  57.     struct hash *slot[1];    /* ``len'' consecutive slot chain pointers */
  58. };
  59. /* hash table entry size in bytes - given the number of slots */
  60. #define table_size(len) \
  61.     (((len)*sizeof(struct hash *)) + OFFSET(hash_table, slot[0]))
  62. /* return TRUE if the hash table slot is empty, not-TRUE otherwise */
  63. #define empty_slot(slot) ((struct hash *)(slot) == NULL)
  64. /* return FALSE if the hash table slot is empty, not-FALSE otherwise */
  65. #define full_slot(slot) ((struct hash *)(slot) != NULL)
  66.  
  67. /*
  68.  * hash flags
  69.  */
  70. #define HASH_CASEFOLD    0x00000001    /* 0 ==> use strcmpic, 1 ==> a != A */
  71. #define HASH_DISKDATA    0x00000002    /* 0 ==> data in mem, 1 ==> on disk */
  72. #define HASH_DISKTBL    0x00000004    /* 0 ==> hashtbl in mem, 1 ==> error */
  73. #define HASH_FLAGMASK    0x00000007    /* logical and of valid flags */
  74. #define HASH_DEFAULT    HASH_CASEFOLD    /* use strcmpic, everything in memory */
  75.  
  76. /*
  77.  * hash:
  78.  *    variable length hash table structure found in hash slot chains
  79.  *
  80.  * Hash slot chains may be a mixture of arrays of ``struct hash'' elements
  81.  * and linked lists of ``struct hash'' elements.  The reason for this mixture
  82.  * is that some of the data is pre-constructed on disk by programs that
  83.  * have no knowledge addresses, and thus simply stack data elements one after
  84.  * another in an array.  Then again, some of the data is malloced and inserted 
  85.  * into lists at run time, and thus must be linked in by pointers.
  86.  *
  87.  * To deal with this problem, the following methods are used:
  88.  *
  89.  *  hash entries in array form:
  90.  *    is_odd(cur->succ) is true
  91.  *    The next entry is hash_len(cur) bytes beyond `cur'
  92.  *
  93.  *  hash entries in queue form:
  94.  *    is_even(cur->succ) is true
  95.  *    cur->succ == NULL ==> end of chain
  96.  *
  97.  * A hash slot chain consists of a set of ``struct hash'' elements whose key
  98.  * strings mapped onto the same hash table slot index.  All hash slot chain
  99.  * elements are kept in sorted order as defined by memcmp().  (smail needs
  100.  * to compare/hash without regard to case, so it uses strcmpic() instead)
  101.  *
  102.  * The location ``element.keystr'' is the starting location of the key string.
  103.  * The length of the key string is ``element.keylen''.  Each key string must
  104.  * be NULL byte terminated.
  105.  *
  106.  * One can may optionally associate data with the element.  The length of
  107.  * this data is found in ``element.datalen''.  Extra bytes may be added to
  108.  * pad the ``element'' to a BYTES_PER_ALIGN byte length.  The first byte of
  109.  * the starting data is located at ``element.keystr[element.keylen]''.
  110.  */
  111. struct hash {
  112.     /* NOTE: succ must be the first element */
  113.     struct hash *succ;     /* pointer to next hash entry, or NULL */
  114.     short keylen;    /* length of key string + '\0' + word boundary pad */
  115.     short datalen;    /* length in bytes of the data beyond the key string */
  116.     char keystr[1];    /* padded key string, optionally followed by data */
  117. };
  118.  
  119. /* hash_align aligns objects on optimal addresses */
  120. #define hash_align(val) (((int)(val)+(BYTES_PER_ALIGN-1))&~(BYTES_PER_ALIGN-1))
  121. /* correctly padded length of the key string - given the key string */
  122. #define keystr_len(keystring) \
  123.   hash_align(strlen((char *)(keystring))+1)
  124. /* hash slot size in bytes - given lengths of the padded key string and data */
  125. #define hashslot_size(keystrlen,datalen) \
  126.  (hash_align(OFFSET(hash, keystr[0]) + \
  127.          hash_align((int)(keystrlen)+1) + \
  128.          hash_align((int)(datalen))))
  129. /* hash slot length in bytes - given a ``struct hash'' element pointer */
  130. #define hash_len(cur) \
  131.  (OFFSET(hash, keystr[0]) + \
  132.   (int)(((struct hash *)(cur))->keylen) + \
  133.   hash_align((((struct hash *)(cur))->datalen)))
  134.  
  135. /* pointer to hash data - given a ``struct hash'' element pointer */
  136. #define hash_data(cur) \
  137.  ((((struct hash *)(cur))->datalen > 0) ? \
  138.   ((char *)(((struct hash *)(cur))->keystr+((struct hash *)(cur))->keylen)) :\
  139.   ((char *)NULL))
  140.  
  141. /*
  142.  * stringcmp - compare two strings
  143.  *
  144.  * Some hash tables compare strings without regard to case while
  145.  * others treat case as significant.  Returns <0, ==0, >0 if str1
  146.  * is less than, equal to, or greater than str2.
  147.  *
  148.  * args:
  149.  *    str1    - char *
  150.  *          first string to compare
  151.  *    str2    - char *
  152.  *          second string to compare
  153.  *    strcase    - int
  154.  *          case == 0 ==> use strcmp,  == 1 ==> use strcmpic
  155.  */
  156. #define stringcmp(str1, str2, strcase) \
  157.     (strcase ? strcmpic(str1, str2) : strcmp(str1, str2))
  158.  
  159. /*
  160.  * hash_string - hash string with or without regard to case
  161.  *
  162.  * args:
  163.  *    str    - char *
  164.  *          the string to hash
  165.  *    mod    - int
  166.  *          prime modulus used in hashing
  167.  *    strcase    - int
  168.  *          == 0 ==> hash where a == A, == 1 ==> hash where a != A
  169.  */
  170. #define hash_string(str, mod, strcase) \
  171.     (strcase ? hash_stric(str, mod) : hash_str(str, mod))
  172.  
  173. /*
  174.  * insert_hash - insert an element before our current location in a slot chain
  175.  *
  176.  * Insert an element after an element (or hash slot head) in a chain.  We
  177.  * pass `prev', a pointer to the `struct hash'-pointer that refers to 
  178.  * our current chain location.  Our job is to have `prev' point to the
  179.  * new element and our new element point to the current chain location.
  180.  *
  181.  * args:
  182.  *    prev    - struct hash **
  183.  *          the entry before the place of insertion.  This pointer
  184.  *          may actually be the hash table slot pointer.
  185.  *    item    - struct hash *
  186.  *          the item to insert
  187.  */
  188. #define insert_hash(prev, item) { \
  189.     *(struct hash **)(item) = *((struct hash **)(prev)); \
  190.     *(struct hash **)(prev) = (struct hash *)(item); \
  191. }
  192.  
  193. /*
  194.  * delete_hash - delete an element in the hash chain
  195.  *
  196.  * Given two ``struct hash'' elements `prev' and `item', delete_hash() will
  197.  * remove `item' from the hash slot chain.
  198.  *
  199.  * input:
  200.  *    prev    - struct hash **
  201.  *          pointer to the previous chain's forward pointer.  This
  202.  *          pointer may actually be the hash hash table slot pointer.
  203.  *          We will delete the element to which this pointer points.
  204.  *    cur    - struct hash *
  205.  *          the `next' pointer of the item to delete
  206.  */
  207.  
  208. #define delete_hash(prev, cur) { \
  209.   *(struct hash **)(prev) = ((struct hash *)(cur))->succ; \
  210. }
  211.  
  212. /*
  213.  * replace_hash - replace an element in the hash chain
  214.  *
  215.  * Replace the element referred by `cur' and pointer at by `prev' with the
  216.  * entry `item'
  217.  *
  218.  * input:
  219.  *    prev    - struct hash *
  220.  *          the previous chain's forward pointer.  This pointer may
  221.  *          actually be the hash table slot pointer.  We will replace
  222.  *          the element to which this pointer points at.
  223.  *    cur    - struct hash *
  224.  *          the element being replaced (i.e., deleted)
  225.  *    item    - struct hash *
  226.  *          the element which is replacing `cur'
  227.  */
  228. #define replace_hash(prev, cur, item) { \
  229.     ((struct hash *)(item))->succ = ((struct hash *)(cur))->succ; \
  230.     (prev) = (struct hash *)(item); \
  231. }
  232.  
  233. /*
  234.  * hash_addr - return memory address of a 'succ' value
  235.  *
  236.  * If 'succ' is an array pointer form, hash_addr() will convert it to
  237.  * a memory address, otherwise the queue pointer is returned.
  238.  *
  239.  * input:
  240.  *    aqval    - struct hash *
  241.  *          the array or queue value tp be converted to a pointer
  242.  *    table    - struct hash_table *
  243.  *          the hash table holding `cur'
  244.  * output:
  245.  *    a pointer to the object reference by succ
  246.  */
  247. #define hash_addr(aqval, table) \
  248.   (is_odd((struct hash *)(aqval)) ? \
  249.     (struct hash *)((char *)(table) + to_even((struct hash *)(aqval))) :\
  250.     (struct hash *)(aqval))
  251.  
  252. /*
  253.  * next_hash - return the next element in a hash slot chain
  254.  *
  255.  * returns NULL if the next element was beyond the end of the chain
  256.  *
  257.  * input:
  258.  *    cur    - struct hash *
  259.  *          our current location
  260.  *    table    - struct hash_table *
  261.  *          the hash table holding `cur'
  262.  * output:
  263.  *    a pointer to the next element, or NULL if no next element
  264.  */
  265. #define next_hash(cur, table) hash_addr(cur->succ, table)
  266.